To maximize performance, Binary Search relies on specific logical conditions to guarantee that roughly $n/2$ elements are eliminated in every loop iteration.
- The core of the procedure involves continuously updating the boundaries (low and high) based on comparing the pivot element $A[mid]$ against the target $t$.
- Comparison Outcomes (The Logic of Division):
- Case 1: Match Found ($A[mid] == t$): The algorithm terminates successfully, returning the index mid.
- Case 2: Target is Larger ($A[mid] < t$): The target must lie to the right. We update the lower bound: low = mid + 1.
- Case 3: Target is Smaller ($A[mid] > t$): The target must lie to the left. We update the upper bound: high = mid - 1.
- Termination Condition: The search continues as long as low <= high. If the boundaries cross (low > high), the search interval is empty, and the target $t$ is not present in $A$.
Binary Search Logic
| Condition | Action | Resulting Search Space |
|---|---|---|
| $A[mid] == t$ | Return `mid` | Target Found |
| $A[mid] < t$ | `low = mid + 1` | Right Half |
| $A[mid] > t$ | `high = mid - 1` | Left Half |